#include <iostream>
#include <chrono>
using namespace std;

int n = 15;
int cnt;

void Dfs(int row, int shu, int pie, int na)
{
    int ave = ((1 << n) - 1) & ~(shu | pie | na);
    while (ave)
    {
        int p = ave & -ave;
        ave ^= p;
        if (row == n)
            ++cnt;
        else
            Dfs(row + 1, shu | p, (pie | p) >> 1, (na | p) << 1);
    }
}

int main()
{
    auto start = std::chrono::system_clock::now();
    Dfs(1, 0, 0, 0);
    auto end = std::chrono::system_clock::now();
    cout << cnt << endl;
    cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << endl;
}
